package tree;

/**
 * 106. 从中序与后序遍历序列构造二叉树
 * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，
 * 请你构造并返回这颗二叉树。
 *
 * 限制
 * 1 <= inorder.length <= 3000
 * postorder.length == inorder.length
 * -3000 <= inorder[i], postorder[i] <= 3000
 * inorder和postorder都由 不同 的值组成
 * postorder中每一个值都在inorder中
 * inorder保证是树的中序遍历
 * postorder保证是树的后序遍历
 */
public class ConstructTree_106 {
    // 自顶向下，先更新根节点，再更新子树
    // 中序遍历：左根右，后序遍历：左右根，后序遍历数组的最后一个元素是根节点
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return build(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
    }

    // 全闭合区间
    public TreeNode build(int[] inorder, int[] postorder, int inorderLeft, int inorderRight, int postorderLeft, int postorderRight) {
        // 由于是全闭合区间，所以左右区间的值可以相等
        if (inorderLeft > inorderRight || postorderLeft > postorderRight) {
            return null;
        }

        // 后序遍历最后一个元素就是根节点
        int rootVal = postorder[postorderRight];
        TreeNode root = new TreeNode(rootVal);

        // 找到根节点在中序遍历数组中的位置，根节点左边是左子树，右边是右子树
        int rootIndex = -1;
        for (int i = inorderLeft; i <= inorderRight; i++) {
            if (inorder[i] == rootVal) {
                rootIndex = i;
            }
        }

        // 计算出左子树的节点个数，这决定了他在中序遍历数组和后序遍历数组中的索引
        int cnt = rootIndex - inorderLeft;

        // 以下每一个索引值都需要仔细推敲，例如postorderLeft + cnt, postorderRight - 1
        root.left = build(inorder, postorder, inorderLeft, inorderLeft + cnt - 1, postorderLeft, postorderLeft + cnt - 1);
        root.right = build(inorder, postorder, rootIndex + 1, inorderRight, postorderLeft + cnt, postorderRight - 1);
        return root;
    }
}
